package com.dy.排序和搜索.中级.前K个高频元素;

import org.omg.CORBA.INTERNAL;

import java.util.*;

/*
前K个高频元素
给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:

输入: nums = [1], k = 1
输出: [1]
说明：

你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
 */
public class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        List<Map.Entry<Integer, Integer>> list = new ArrayList<>(map.entrySet());
        list.sort(new Comparator<Map.Entry<Integer, Integer>>() {
            @Override
            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                return o2.getValue() - o1.getValue();
            }
        });

        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            res.add(list.get(i).getKey());
        }
        return res;
    }

    //堆
    public List<Integer> topKFrequent2(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        //最小堆，根据次数
        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return map.get(o1) - map.get(o2);
            }
        });

        for (int key : map.keySet()) {
            if (pq.size() < k) {
                pq.add(key);
            } else {
                if (map.get(key) > map.get(pq.peek())) {
                    pq.remove();
                    pq.add(key);
                }
            }
        }
        List<Integer> res = new ArrayList<>();
        while (!pq.isEmpty()) {
            res.add(pq.remove());

        }
        return res;

    }

    //桶排序
    public List<Integer> topKFrequent3(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        //创建bucket 的list数组,每个元素频次相同
        List<Integer>[] bucket = new List[nums.length + 1];
        for (int key : map.keySet()) {
            int freq = map.get(key);
            if (bucket[freq] == null) {
                bucket[freq] = new ArrayList<>();
            }
            bucket[freq].add(key);
        }
        List<Integer> res = new ArrayList<>();
        for (int i = bucket.length - 1; i >= 0; i--) {
            if (res.size() < k &&bucket[i]!=null) {
                res.addAll(bucket[i]);
            }
        }
        return res;

    }
//        Map<Integer,Integer> map = new HashMap<>();
//        for(int i=0;i<nums.length;i++){
//            if(map.containsKey(nums[i])){
//                map.put(nums[i],map.get(nums[i])+1);
//            }
//            else{
//                map.put(nums[i],1);
//            }
//        }
//        List<Map.Entry<Integer,Integer>> list = new ArrayList<>(map.entrySet());
//
//        Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>() {
//            @Override
//            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
//                // 返回值为int类型，大于0表示正序,从小到达，小于0表示逆序，从大到小
//                return o2.getValue() - o1.getValue();
//            }
//        });
//        List<Integer> res = new ArrayList<>();
//        for(int i=0;i<k;i++){
//            res.add(list.get(i).getKey());
//        }
//        return res;
//    }
//    /*
//    借助堆这种数据结构。通过维护一个元素数目为 k 的最小堆，每次都将新的元素与堆顶端的元素（堆中频率最小的元素）进行比较，
//    如果新的元素的频率比堆顶端的元素大，则弹出堆顶端的元素，将新的元素添加进堆中。
//    最终，堆中的 k 个元素即为前 k 个高频元素。
//    堆存的是key，在新建优先队列时，重写compare，比较value的大小
//     */
//    public List<Integer> topKFrequent2(int[] nums, int k) {
//        // 统计元素的频率
//        Map<Integer, Integer> map = new HashMap<>(16);
//        for (int num : nums) {
//            map.put(num, map.getOrDefault(num, 0) + 1);
//        }
//
//        // 遍历map，用最小堆保存频率最大的k个元素
//        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
//            @Override
//            public int compare(Integer a, Integer b) {
//                return map.get(a) - map.get(b);
//            }
//        });
//
////        PriorityQueue<Integer> pq = new PriorityQueue<>(
////                (a, b) -> map.get(a) - map.get(b)
////        );
//        for (Integer key : map.keySet()) {
//            if (pq.size() < k) {
//                pq.add(key);
//            } else if (map.get(key) > map.get(pq.peek())) {
//                pq.remove();
//                pq.add(key);
//            }
//        }
//
//        // 取出最小堆中的元素
//        List<Integer> ret = new ArrayList<>();
//        while (!pq.isEmpty()) {
//            ret.add(pq.remove());
//        }
//
//        return ret;
//    }
//    /*
//    桶排序（bucket sort）
//思路
//最后，为了进一步优化时间复杂度，可以采用桶排序（bucket sort），即用空间复杂度换取时间复杂度。
//
//第一步和解法二相同，也是统计出数组中元素的频次。
//接着，将数组中的元素按照出现频次进行分组，即出现频次为 i 的元素存放在第 i 个桶。
//最后，从桶中逆序取出前 k 个元素。
//     */
//    public List<Integer> topKFrequent3(int[] nums, int k) {
//        // 统计元素的频次
//        Map<Integer, Integer> int2FreqMap = new HashMap<>(16);
//        for (int num : nums) {
//            int2FreqMap.put(num, int2FreqMap.getOrDefault(num, 0) + 1);
//        }
//
//        // 桶排序
//        List<Integer>[] bucket = new List[nums.length + 1];
//        for (Integer key : int2FreqMap.keySet()) {
//            int freq = int2FreqMap.get(key);
//            if (bucket[freq] == null) {
//                bucket[freq] = new ArrayList<>();
//            }
//            bucket[freq].add(key);
//        }
//
//        // 逆序（频次由高到低）取出元素
//        List<Integer> ret = new ArrayList<>();
//        for (int i = nums.length; i >= 0 && ret.size() < k; --i) {
//            if (bucket[i] != null) {
//                ret.addAll(bucket[i]);
//            }
//        }
//
//        return ret;
//    }
}
